package com.hard;

/**
 * Created by Lxk on 2020/1/26.
 */
public class Solution45 {

    public int jump(int[] nums) {
        if (nums.length == 1) {
            return 0;
        }
        int lastEndPos = nums[0];
        int lastBeginPos = 1;
        int count = 1;
        while (lastEndPos < nums.length - 1) {
            int lastPos = lastBeginPos;
            int lastPosVal = lastEndPos;
            for (int k = lastBeginPos; k <= lastEndPos; k++) {
                int newLastEndPos = k + nums[k];
                if (newLastEndPos > lastPosVal) {
                    lastPos = k;
                    lastPosVal = newLastEndPos;
                }
            }
            if (Integer.valueOf(lastPosVal).equals(lastEndPos)) {
                return 0;
            }
            count++;
            lastEndPos = lastPosVal;
            lastBeginPos = lastPos + 1;
        }
        return count;
    }

    public static void main(String[] args) {
        int[] arr = {0};
        Solution45 solution45 = new Solution45();
        System.out.println(solution45.jump(arr));
    }

}
